\subsection{Normalization Component}
C/C++ allows the program accesses the data structure field
flexibly~\cite{PLP}: it can access the field by the name resolution,
pointer arithmetic with its offset or even the absolute address if
the base address of the data structure is fixed. To guarantee the
execution correctness of the program under the data structure
randomization of SALADS, we normalize the data structure field
memory access based on the following assumption: the field with the
fixed address can not be randomized; if the field address is
calculated by the other field's address in the same data structure,
both of them can not be randomized or if the field is calculated by
other pointer which points to the outside of the data structure the
field resides, the field can not be randomized; if the field's
offset is pre-calculated before used or the field is referenced by
other pointer, we mark the field can not be randomized. Figure
~\ref{fig:abnormal} demonstrates three contradictive examples.
Figure~\ref{fig:abnormal}(a) shows the source code from
Linux-2.6.23.1 which calculates the address of \texttt{pt\_regs}
from \texttt{thread\_info} (beginning of the kernel stack and end of
the kernel stack), from the memory layout, we can see the addresses
of \texttt{pt\_regs} and \texttt{thread\_info} are fixed, as such
when \texttt{pt\_regs} or \texttt{thread\_info} is declared as the
field of other data structure, we can not randomize the field.
Figure~\ref{fig:abnormal}(b) represents another contradictive
example, the field \texttt{serial\_header\_t} in
\texttt{message\_header\_t} is calculated by the field
\texttt{data}, as such we mark the fields
\texttt{message\_header\_t} and \texttt{data} in \texttt{message\_t}
can not be randomized. Figure~\ref{fig:abnormal}(c) illustrates
another example that the offsets of fields in \texttt{info} is
calculated, as such we can not randomize the fields in
\texttt{info}. For the first example in Figure
~\ref{fig:abnormal}(a), we can not randomize the field with
\texttt{thread\_info} or \texttt{pt\_regs} type since its address is
fixed, if we randomize it, program can not access the field by the
default absolute address. For the second example in Figure
~\ref{fig:abnormal}(b), the relative address between the two fields
are fixed, if the field is randomized, the relative address is
changed, and will lead the memory inconsistency when accessing one
from the other. For the third example in Figure
~\ref{fig:abnormal}(c), the offset of the field is pre-calculated
either explicitly recording the offset or even implicitly saving the
field's address to one pointer.



\begin{figure*}[t]
\centering
\includegraphics[scale=0.8]{abnormal.eps}
\caption{Abnormal Data Structure Access} \label{fig:abnormal}
\end{figure*}
Since SALADS finds the cases in the program falling into the three
categories in Figure~\ref{fig:abnormal} and marks the field as
non-randomizable, SALADS guarantees all the fields that can be
randomized in a struct are accessed from the reference or pointer to
the entry of the struct based on the fields' name or offset. We
implement the normalization component by three steps: first SALADS
finds the field offset (e.g. Figure~\ref{fig:abnormal}(c)) and the
pointer points to the field during AST parsing, and marks the field
as non-randomizable. This step generates the pairs in the form of
\texttt{<$\tau_p$,a>}, in which $\tau_p$ is the data structure type
and \texttt{a} is the name of the field. Based on these pairs,
SALADS will not randomize the fields by the randomization component
at runtime. After this step, SALADS can guarantee the field which is
accessed by the explicit fixed offset can not be randomized; second,
SALADS finds the field that has fixed address by intercepting the
hard-coded value (THREAD\_SIZE in Figure~\ref{fig:abnormal}(a))
which is used by the pointer (task\_stack\_page(p) in
Figure~\ref{fig:abnormal}(a))
 to the field (pt\_regs) or explicitly allocated
to a fixed address by the program (e.g. the memory allocation API
\texttt{alloc\_thread\_info} for \texttt{thread\_info} during the
AST passing, after this step, SALADS sets
 all the field with fixed address non-randomizable and let the randomization component not randomize the data structure field; third, SALADS extends the pointer arithmetic option ``-fpointer-arith" of GCC, combining the alias analysis component and randomization component, to find the abnormal field access by the pointer arithmetic from the inside or outside of the data structure based on the following method at runtime.%and extend the



SALADS finds all the data structure instances occurring in the
program till the current execution statement: named \texttt{{I}},
and we can calculate the size of the data structure and the start
address of the data structure instance. Thus the memory range of the
data structure instance is [$I_a$, $S_z$]. $S_z$ is the size of the
data structure, which can be calculated during the \emph{extraction
component}. We must point out that the GIMPLE language only allows
single-level pointers~\cite{GCCOV}, so for each gimple statement,
the pointer arithmetic operation can be represented as [Ptr, Int].
In order to reduce the pointer arithmetic operations that are
checked, we use the result of the alias analysis component, and only
check the pointers that are related to the data structure instance.
The implementation of alias analysis component will be illustrated
in Section 3.3. We set the following assert at runtime, if the
pointer arithmetic meets with the assert (1), we check whether the
Ptr or Ptr+Int point to certain data structure field, if so we mark
the field as non-randomizable. Take Figure 3(b) for example, Ptr is
the msg$\rightarrow$data and Ptr+Int is the
msg$\rightarrow$header[6], as such data and header in struct
\texttt{message\_t} can not be randomized.

Recently, to guarantee the safety of the pointer arithmetic, some
research organization proposes the constraint that allows the
pointer arithmetic for the array~\cite{CERT}, but the pointer
arithmetic can not be used for the non-array object including the
struct. If the ANSI C can adopt this strict constraint, SALADS can
guarantee the correct memory access to the randomized struct without
normalization component.

\begin{equation*}
\begin{split}
\forall [Ptr, Int], \exists [I_a,S_z]:   \frac{I_a < Ptr \le
I_a+S_z}{I_a < Ptr+Int \le I_a+S_z}   \lor \frac{Ptr>I_a+S_z \lor
Ptr<I_a}{I_a < Ptr+Int \le I_a+S_z}
\end{split}
\end{equation*}



%\begin{equation}
%\begin{split}
%\forall [Ptr, Int], \exists [I_a,S_z]:  \frac{Ptr = I_a} {I_a \le
%Ptr+Int \le I_a+S_z}   \lor \frac{I_a < Ptr \le I_a+S_z}{Ptr+Int =
%I_a}   \lor \frac{Ptr>I_a+S_z \lor Ptr<I_a}{Ptr+Int>I_a+S_z \lor
%Ptr+Int<I_a}
%\end{split}
%\end{equation}
